# 动态规划
#
# array
# [5, 8, 1, 6, -7, 9, 2]
#
# result
# [5, 8, 8, 14, 14, X]
# [xx, xx, xx, xx, xx, xx, xx]
# result 有和 array 元素个数相同的元素

# 初始状态
# result[0] = array[0]
# result[1] = max(array[0], array[1])
# 递归过程 / 执行公式
# result[2] = max(result[2 - 1], array[2] + result[2 - 2])
# result[3] = max(result[3 - 1], array[3] + result[3 - 2])
# result[4] = max(result[4 - 1], array[4] + result[4 - 2])
# ...
# result[len(array) - 1] = max(result[len(array) - 2], array[len(array) - 1] + result[len(array) - 3])

# result[i] = max(result[i - 1], array[i] + result[i - 2])

# result[0] 表示 array 位置 0 能计算的结果
# result[1] 表示 array 位置 1 能计算的结果
# result[2] 表示 array 位置 1 能计算的结果
# ...
# result[len(array) - 1], array 中最后一个元素能计算出来的


# 5 + 1 + 2
# 8 + 6 + 9

def max_sum(array):
